package MoveWindowAndStack;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

//滑动窗口问题   使用双端队列完成  队列中存储位置 位置所代表的值从左到右递减 可以从两边弹出 只能从右边加入
//通过LinkedList的removeLast()  和  getLast完成对左右头节点的删除
public class MoveWindow {
    public static void main(String[] args) {
        int[] arr = {5,1,2,3,3,4,8,9,2,4};
        ArrayList<Integer> arrayList = moveWindow(arr,3);
        Iterator<Integer> it=arrayList.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }

    public static ArrayList<Integer> moveWindow(int[] arr,int n){
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int a=0;a<arr.length;a++){
            maxHead(linkedList,arr,a,3);
            System.out.println("长度"+linkedList.size()+"第一个为"+linkedList.getFirst());
            arrayList.add(linkedList.getFirst());
        }
        return arrayList;
    }

    public static void maxHead(LinkedList<Integer> linkedList,int[] arr,int n,int w){
        if (linkedList.size()==0){
            linkedList.add(arr[n]);
        }else {
            if (linkedList.size() == w){   //如果窗口里的位置已经满了，除最左边一位剩余全部弹出
                for (int a=0;a<w-1;a++){
                    linkedList.removeLast();
                }
            }
            if (arr[n] <= linkedList.getFirst()){   //如果比头节点小 则加入队列
                linkedList.add(arr[n]);
            }else { //如果比头节点大 则清空队列 将当天位置加入
                while (!linkedList.isEmpty()){
                    linkedList.removeLast();
                }
                linkedList.add(arr[n]);
            }
        }
    }
}